Problem statement: zenit14ski

Plán úniku je prakticky hotový. Najbližšiu noc všetky správne zvieratká utečú zo ZOO. Večer pred útekom sa na prísne tajnom mieste dolaďujú posledné detaily. Jediná vec, ktorá môže celý plán pokaziť je nečakaná inšpekcia strážnika na tomto prísne tajnom mieste. Preto sa zvieratká rozhodli, že pošlú na vhodne určené políčka papagáje. V prípade, že by tieto papagáje spozorovali strážnikov, dajú varovný signál. Pre daný plánik ZOO zistite, koľko najmenej papagájov treba, aby sa žiadny strážnik nemohol dostať zo strážnice do skrýše bez toho, aby prešiel cez políčko s papagájom.

Plánik ZOO má obdĺžnikový tvar mriežky, ktorá pozostáva z priechodných (., bodka) a nepriechodných políčok (#). Medzi dvoma políčkami sa dá prejsť, ak zdieľajú hranu. Každé políčko má teda najviac štyroch susedov. Pre jednoduchosť môžete predpokladať, že okraj plánika je nepriechodný (teda, že na jeho obvode sú samé #). Práve jedno políčko plánika je strážnica S a práve jedno ďalšie políčko je skrýša zvieratiek Z. Môžete predpokladať, že tieto dve políčka nesusedia. Z tohto okrem iného vyplýva, že vždy stačí konečný počet strážnych papagájov.

Formát vstupu a výstupu

Na prvom riadku vstupu sú rozmery mapy \(R\) a \(S\). Tieto čísla sú celé a platí \(5 \leq R,S \leq 100\). Na každom z ďalších \(R\) riadkov je \(S\) znakov. Plánik spĺňa popis uvedený vyššie. Na výstup vypíšte koľko najmenej papagájov treba pri ich vhodnom rozmiestnení. Táto úloha nie je za 55 bodov len tak pre nič za nič. Ak sa vám zda ľahká, porozmýšľajte, či je vaše riešenie správne.

Príklady

Input:

5 5
#####
#S..#
###.#
#Z#.#
#####

Output:

0

Tu sa nedá prejsť zo strážnice do skrýše aj bez toho, aby sme použili nejakých papagájov.

Input:

6 6
######
#...Z#
#.#..#
##...#
#.S#.#
######

Output:

1

Input:

9 27
###########################
#.........................#
#.#######################.#
#.#.....................#.#
#.#.###################.#.#
#..Z...................S..#
###.###################.###
###.....................###
###########################

Output:

4